#include "game.h"
#include<iostream>
#include<cstdio>
#include<vector>
int p[5005],vis[5005],cnt,d[5005],num,rc,n;
std::pair<int, int> pr[5005];
std::vector<int> vec;
void get_ans(int l,int r)
{
    for(int i=l;i<=r;i++) std::swap(vec[pr[i].first-1],vec[pr[i].second-1]);
    int nc=count(vec);
    if(nc-rc==0)
    {
        for(int i=l;i<=r;i++) std::swap(vec[pr[i].first-1],vec[pr[i].second-1]);
        return;
    }
    for(int i=l;i<=r;i++) std::swap(vec[pr[i].first-1],vec[pr[i].second-1]);
    if(l==r)
    {
        if(nc-rc==2)
        {
            vis[pr[l].first]=vis[pr[l].second]=1,num-=2;
            std::swap(vec[pr[l].first-1],vec[pr[l].second-1]);
            rc+=2,nc-=2;
            return;
        }
        if(nc-rc==-2)
        {
            vis[pr[l].first]=vis[pr[l].second]=1,num-=2;
        }
        if(nc-rc==1)
        {
            std::swap(vec[pr[l].first-1],vec[pr[l].second-1]);
            rc++,nc--;
        }
        if(nc-rc==-1)
        {
            for(int i=1;i<=n;i++)
            {
                if(vis[i]==1)
                {
                    std::swap(vec[pr[l].first-1],vec[i-1]);
                    if(count(vec)-rc==-2)
                    {
                        std::swap(vec[pr[l].first-1],vec[i-1]);
                        vis[pr[l].first]=1,num--;
                    }
                    else
                    {
                        std::swap(vec[pr[l].first-1],vec[i-1]);
                        vis[pr[l].second]=1,num--;
                    }
                    return;
                }
            }
            for(int i=1;i<=n;i++)
            {
                if(i==pr[l].first || i==pr[l].second) continue;
                if(vis[i]==0)
                {
                    std::swap(vec[pr[l].first-1],vec[i-1]);
                    if(count(vec)-rc==-1)
                    {
                        std::swap(vec[pr[l].first-1],vec[i-1]);
                        vis[pr[l].first]=1,num--;
                        return;
                    }
                    std::swap(vec[pr[l].first-1],vec[i-1]);
                    std::swap(vec[pr[l].second-1],vec[i-1]);
                    if(count(vec)-rc==-1)
                    {
                        std::swap(vec[pr[l].second-1],vec[i-1]);
                        vis[pr[l].second]=1,num--;
                        return;
                    }
                    std::swap(vec[pr[l].second-1],vec[i-1]);
                }
            }
        }
        return;
    }
    int mid=(l+r)>>1;
    get_ans(l,mid);
    get_ans(mid+1,r);
}
std::vector<int> guess(int N, int limit)
{
    n=N;
    std::mt19937 rnd(time(0));
	num=rc=n;
	for(int i=1;i<=n;i++) p[i]=i,vis[i]=0;
	while(rc>0)
    {
        shuffle(p+1,p+1+n,rnd);
        vec.clear();
        for(int i=1;i<=n;i++) vec.push_back(p[i]);
        rc=count(vec);
    }
    /*std::cout<<"?";
    for(int i=0;i<n;i++) std::cout<<vec[i]<<' ';
    std::cout<<'\n';*/
    while(num>0)
    {
        cnt=0;
        for(int i=1;i<=n;i++)
            if(vis[i]==0) d[++cnt]=i;
        std::mt19937 rd(rnd());
        shuffle(d+1,d+1+cnt,rd);
        for(int i=2;i<=cnt;i+=2) pr[i/2]=std::make_pair(d[i-1],d[i]);
        cnt/=2;
        //for(int i=1;i<=cnt;i++) std::cout<<pr[i].first<<' '<<pr[i].second<<'\n';
        get_ans(1,cnt);
        /*std::cout<<"?";
        for(int i=0;i<n;i++) std::cout<<vec[i]<<' ';
        std::cout<<'\n';
        for(int i=1;i<=n;i++) std::cout<<vis[i]<<' ';
        std::cout<<std::endl;*/
    }
    //assert(count(vec)==n);
	return vec;
}

